During data transferring, in order to let the receiving end to correctly determine the data transmitted by the transmitting end, a data encoding process is usually performed. After the transmitting end encodes the data to be transferred, the transmitting end will then transfer the encoded data through the physical channel. After the receiving end receives the encoded data, the receiving end performs the corresponding decoding process. On one hand, the decoding process is to extract the original source data, and on the other hand, the decoding process is to ensure the correctness of the original data.
Currently, numerous encoding and/or decoding techniques have been developed. For example, parity check bit is added to the end of source data so that the receiving end may determine whether the source data is correct. Or, an error correction code (ECC) part may be further added to the end of the source data so that the receiving end may correct some of the errors in addition to determining whether the data is received correctly.
To enable scalability and fault-tolerance of the encoded data distributed in computer network, Luby developed a new type of encoding, called LT code. FIG. 1 shows an exemplary schematic view of LT code. As shown in FIG. 1, LT code uses a special probability distribution to determine the degree used by each source symbol of a plurality of source symbols 110 during the encoding. The LT code considers a source file as a combination having a plurality of segments of equal size and takes a number (degree) of segments from the plurality of segments to perform XOR to generate encoded data. The LT encoded symbol 120 repeats the encoding operation until the decoder can recover the source file.
Another encoding type is called Raptor. The Raptor code is an extension of the LT code. The Raptor code has the characteristic of linear time encoding and decoding. FIG. 2 shows an exemplary schematic view of the Raptor code. As shown in FIG. 2, the encoding process of Raptor code includes two stages. The first stage is to use low complexity encoding technology to perform one-to-one encoding on a plurality of source file segments, i.e., a plurality of source symbols 210. The second stage is to perform the re-coding on the pre-coded symbol 220 by using the LT coding of FIG. 1. Finally, the Raptor coded symbol 230 is transmitted to the decoder.
In the application of peer to peer (P2P) system, the encoded data will be relayed between the peers. Each peer will re-code the received encoded data and then relayed to other peers. Therefore, with Raptor code, a plurality of multi-layered steps must be taken to decode.
Network coding is a technique for relaying files in a multi-path network. FIG. 3 shows an exemplary schematic view of the application of network coding technique in a distributed network. In FIG. 3, the receiving-end peers, such as, R1-R4, receive encoded packets from one or more peers, such as, C1-C8, delivered through multi-layered router to the designated destination peer, i.e., some of peers R1-R4, so that the destination peer may recover the source file. The encoded packet will be re-coded every time the packet passes through a single-layered router for transferring. For example, through two-layered of router routing, peer R1 receives the encoded packet from peers C1 and C5 and encoded packet from peers C2 and C6. In other words, the encoded packet will be re-coded every time the packet passes a single-layered router for transferring. This technique uses the random number within the same finite field during encoding and decoding.
In addition to protect the data transferring, the network coding technique may also utilize the bandwidth of the network efficiently. The data through the multi-path transmission may refer to each other and further decoding the source data via encoded data computation. Among the network encoding techniques, a technique is called random linear network coding (RLNC) technique. The RLNC technique uses a multi-bit finite field computation as a basis of encoding and decoding. The generated complex computation will reduce the data transmission throughput and the decoding rate.
Another technique is called binary network coding (BNC) technique, using XOR computation as the basis for encoding and decoding. In comparison with the RLNC technique, the BNC technique reduces the amount of computation and has a lower data transmission overhead as well as a more efficient encoding computation. When using the BNC technique, the transmission end must supply to transmit more data whenever there is a data loss during the transmission.
In the network coding techniques, the encoder divides the source file into N segments, and computes the linear combination N times for all the segments respectively to generate different main encoded data. The decoder may use matrix computation to recover the N main encoded data back to the source file. However, the individual encoded data may have mutual linear dependency, leading to invalid encoded data. Therefore, the decoder must transmit k additional encoded data so that the decoder can find N mutually linear independent encoded data from the received N+k data, and further recover back to the source file.
If the N main encoded data and k additional encoded data all use the finite field of smaller space, such as, Galois Field (GF(2)), the computation of encoding and decoding may be accomplished more efficiently. However, because a smaller space may easily lead to linear dependent encoded data, therefore, a larger k is required to ensure the existence of the N linear independent encoded data, and a higher transmission cost is required. On the other hand, if the N main encoded data and k additional data all use the finite field of a larger space, such as, GF(28), the required transmission cost will be reduced because the encoded data is not easy to be dependent. However, the encoding and decoding computation will increase, too.